package oj.oj_21;

import oj.ListNode;

/**
 * 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode.cn/problems/merge-two-sorted-lists/submissions/
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head1=list1;
        ListNode head2=list2;
        // 结果链表的头结点 和 尾结点
        ListNode head=new ListNode(); // 工具结点
        ListNode last=head;   // 由于现在结果链表中只有一个结点，所以尾结点就是头结点
        while (head1!=null&&head2!=null){
            // head1 代表的链表不是 empty 并且 head2 代表的链表不是 empty
            if(head1.val<=head2.val){
                // 将 head1 代表的链表头删
                ListNode cur=head1;
                head1=head1.next;
                // 将结点尾插到结果链表中
                last.next=cur;
                last=cur;
            }
            else{
                ListNode cur=head2;
                head2=head2.next;
                // 将结点尾插到结果链表中
                last.next=cur;
                last=cur;
            }
        }
        if(head1!=null){
            last.next=head1;// 把 head1 接到结果链表的后边
        }
        else{
            last.next=head2;
        }
        return head.next;// 跳过工具结点即可
    }
    public static void main(String[] args) {//测试样例
        ListNode listN1 = new ListNode(100);
        ListNode listN2 = new ListNode(200);
        ListNode listN3 = new ListNode(300);

        listN1.next = listN2;
        listN2.next = listN3;

        ListNode list1 = null;
        ListNode list2 = null;

        Solution solution = new Solution();
        ListNode ans = solution.mergeTwoLists(list1, list2);
    }
}
